public class TextDemo {
    static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val = val;
        }
    }
    public int findPeak(int[] nums){
        int n = nums.length;
        int index = (int)(Math.random()*n);

        while(!(compare(nums,index-1,index)<=0) && compare(nums,index,index+1)<0){
            if(compare(nums,index,index+1)<0){
                index+=1;
            }else{
                index-=1;
            }
        }
        return index;
    }
    public int compare(int[] nums,int index1,int index2){
        int[] num1 = get(nums,index1);
        int[] num2 = get(nums,index2);
        if(num1[0]!=num2[0]){
            return num1[0] > num2[0] ? 1 : -1;
        }
        if(num1[1]==num2[1]){
            return 0;
        }
        return num1[1]>num2[1]?1:-1;
    }
    public int[] get(int[] nums,int index){
        if(index==-1 || index == nums.length){
            return new int[]{0,0};
        }
        return new int[]{1,nums[index]};
    }
    public static ListNode deleteDuplicates (ListNode head) {
        // write code here
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode cur = head;
        while(cur!=null && cur.next!=null&&prev!=null){
            if(cur.val==cur.next.val){
                prev.next = cur.next.next;
                prev = prev.next;
            }else{
                cur = cur.next;
                prev = prev.next;
            }
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode cur = head;
        cur.next = new ListNode(2);
        cur = cur.next;
        cur.next = new ListNode(2);
        deleteDuplicates(head);
    }
    public ListNode oddEvenList (ListNode head) {
        // write code here
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            if(fast.next.val%2!=0){
                ListNode next = fast.next;
                fast.next = next.next;
                next.next = slow.next;
                slow.next = next;
                slow = slow.next;
            }
            fast = fast.next;
        }
        if(head.val%2==0){
            fast = head;
            head = head.next;
            fast.next = slow.next;
            slow.next = fast;
        }
        return head;

    }
    private ListNode merge(ListNode head1,ListNode head2){
        if(head1==null || head2==null){
            return head1==null?head2:head1;
        }
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while(head1!=null && head2!=null){
            if(head1.val<=head2.val){
                cur.next = head1;
                head1 = head1.next;
            }else{
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        if(head1!=null){
            cur.next = head1;
        }else{
            cur.next = head2;
        }
        return head.next;
    }
    public ListNode sortInList (ListNode head) {
        // write code here
        if(head==null || head.next==null){
            return head;
        }
        ListNode left = head;
        ListNode middle = head.next;
        ListNode right = head.next.next;

        while(right!=null && right.next!=null){
            left = left.next;
            middle = middle.next;
            right = right.next.next;
        }
        left.next = null;
        return merge(sortInList(head),sortInList(middle));
    }
    //2 4 7 1    3 0 2 6 9
    //1 2 4 7
    public static ListNode sortInList1 (ListNode head) {
        // write code here
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        ListNode cur = dummy;
        while(cur!=null&& cur.next!=null){
            if(cur.val<=cur.next.val){
                cur = cur.next;
            }else{
                ListNode prev = dummy;
                int tem = cur.next.val;
                while(prev.next!=cur && tem>prev.next.val){
                    prev = prev.next;
                }
                ListNode next = cur.next;
                cur.next = next.next;
                next.next = prev.next;
                prev.next = next;
                cur = next;
            }
        }
        return dummy.next;
    }


    private ListNode reverse(ListNode head){
        ListNode prev = null;
        ListNode next = null;
        ListNode cur = head;
        while(cur!=null){
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    //2 4 7 1 3 0 2 6 9
    //1 2 4 7 3 0 2 6 9
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1==null || head2==null){
            return head1==null ?head2 :head1;
        }
        head1 = reverse(head1);
        head2 = reverse(head2);
        int tem = 0;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(head1!=null || head2!=null || tem!=0){
            if(head1!=null){
                tem+=head1.val;
                head1 = head1.next;
            }
            if(head2!=null){
                tem+=head2.val;
                head2 = head2.next;
            }
            cur.next = new ListNode(tem%10);
            cur = cur.next;
            tem = tem/10;
        }
        cur = dummy.next;
        dummy.next = null;
        return reverse(cur);
    }
}
